package day_2022_4_to_7.day48;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 求正数数组的最小不可组成和
 *
 * @author haomin
 * @date 2022/05/27 17:07
 **/
public class Day29_1_GetSumFromArr {
    public int getFirstUnFormedNum(int[] arr) {
        Arrays.sort(arr);
        int min = arr[0];
        int max = arr[0];
        ArrayList<Integer> result = new ArrayList<>();
        getNumber(arr,result,0, 0);
        for (int i = 1; i < arr.length; i++) {
            max += arr[i];
        }
        for (int i = min + 1; i < max; i++) {
            if (!result.contains(i)) {
                return i;
            }
        }
        return max + 1;
    }

    private void getNumber(int[] arr,ArrayList<Integer> result, int pos, int sum) {
        if (pos == arr.length) {
            return;
        }
        for (int i = pos; i < arr.length; i++) {
            sum += arr[i];
            result.add(sum);
            getNumber(arr,result,i + 1, sum);
            sum -= arr[i];
        }
    }
}